# -*- coding: utf-8 -*-

# 问题描述：
# 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数
# 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用

# 示例:
# 给定 nums = [2, 7, 11, 15], target = 9
# 因为 nums[0] + nums[1] = 2 + 7 = 9
# 所以返回 [0, 1]

# 解决方案1：
# 最容易想到的暴力破解的方法，先通过target - nums[0]获取第二个数，然后遍历数组检查第二个数是否存在
# 正解：
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for index_1 in range(len(nums)):
            to_find_value = target - nums[index_1];
            for index_2 in range(index_1 + 1, len(nums)):
                if(to_find_value == nums[index_2]):
                    return [index_1, index_2];
        return None;

# # 解决方案2：
# # 先对数组进行排序[非递减序列]，然后从数组的2端开始遍历，如果比target大则移动最大端，如果比target小则移动最小端，相对方案1，能降低算法的时间复杂度
# # 正解：
# class Solution(object):
#     def twoSum(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: List[int]
#         """
#         sorted_nums = sorted(nums);

#         index_begin = 0;
#         index_end = len(nums) - 1;

#         while index_begin < index_end:
#             sum_begin_end = sorted_nums[index_begin] + sorted_nums[index_end];
#             if sum_begin_end == target:
#                 break;
#             elif sum_begin_end > target:
#                 index_end = index_end - 1;
#             elif sum_begin_end < target:
#                 index_begin = index_begin + 1;

#         if index_begin < index_end:
#             index_1 = 0;
#             index_2 = 0;

#             for index in range(len(nums)):
#                 if nums[index] == sorted_nums[index_begin]:
#                     index_1 = index;
#                     break;

#             for index in range(len(nums)):
#                 if nums[index] == sorted_nums[index_end] and index_1 != index:
#                     index_2 = index;
#                     break;

#             return [index_1, index_2];
#         return None;

# # 遇到的问题：
# # 1：第一步排序已经打乱了nums原本的排序，返回结果时，返回的却是排序后的下标
# class Solution(object):
#     def twoSum(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: List[int]
#         """
#         nums = sorted(nums);

#         index_begin = 0;
#         index_end = len(nums) - 1;

#         while index_begin < index_end:
#             sum_begin_end = nums[index_begin] + nums[index_end];
#             if sum_begin_end == target:
#                 return [index_begin, index_end];
#             elif sum_begin_end > target:
#                 index_end = index_end - 1;
#             elif sum_begin_end < target:
#                 index_begin = index_begin + 1;

#         return None;

# # 2：对于拥有相同元素的数组，如[3, 3]返回的结果是[0, 0]是错误的
# class Solution(object):
#     def twoSum(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: List[int]
#         """
#         sorted_nums = sorted(nums);

#         index_begin = 0;
#         index_end = len(nums) - 1;

#         while index_begin < index_end:
#             sum_begin_end = sorted_nums[index_begin] + sorted_nums[index_end];
#             if sum_begin_end == target:
#                 break;
#             elif sum_begin_end > target:
#                 index_end = index_end - 1;
#             elif sum_begin_end < target:
#                 index_begin = index_begin + 1;

#         if index_begin < index_end:
#             index_1 = 0;
#             index_2 = 0;

#             for index in range(len(nums)):
#                 if nums[index] == sorted_nums[index_begin]:
#                     index_1 = index;
#                     break;

#             for index in range(len(nums)):
#                 if nums[index] == sorted_nums[index_end]:
#                     index_2 = index;
#                     break;

#             return [index_1, index_2];
#         return None;

t = Solution();
print t.twoSum([3, 3], 6);




# # 阅读官方提供的答案
# # 方案1：
# public int[] twoSum(int[] nums, int target) {
#     Map<Integer, Integer> map = new HashMap<>();
#     for (int i = 0; i < nums.length; i++) {
#         map.put(nums[i], i);
#     }
#     for (int i = 0; i < nums.length; i++) {
#         int complement = target - nums[i];
#         if (map.containsKey(complement) && map.get(complement) != i) {
#             return new int[] { i, map.get(complement) };
#         }
#     }
#     throw new IllegalArgumentException("No two sum solution");
# }

# # 方案2：
# public int[] twoSum(int[] nums, int target) {
#     Map<Integer, Integer> map = new HashMap<>();
#     for (int i = 0; i < nums.length; i++) {
#         int complement = target - nums[i];
#         if (map.containsKey(complement)) {
#             return new int[] { map.get(complement), i };
#         }
#         map.put(nums[i], i);
#     }
#     throw new IllegalArgumentException("No two sum solution");
# }
# # 学习到的内容：
# # 利用哈希的特性，把原本需要时间复杂度为n的查找，变为了时间复杂度为1的查找